# 47.全排列II
# 给定一个可包含重复数字的序列nums ，按任意顺序返回所有不重复的全排列。
#
# 示例1：
# 输入：nums = [1, 1, 2]
# 输出：
# [[1, 1, 2],
#  [1, 2, 1],
#  [2, 1, 1]]
#
# 示例2：
# 输入：nums = [1, 2, 3]
# 输出：[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]


class Solution:
    def permuteUnique(self, nums: [int]):
        res = []
        path = []
        used = [0] * len(nums)
        def backtracking(nums,used):
            if len(path) == len(nums):
                tmp = path[:]
                if tmp not in res:
                    res.append(tmp)
                return
            for i in range(0,len(nums)):
                if used[i] == 1:
                    continue
                used[i] = 1
                path.append(nums[i])
                backtracking(nums,used)
                used[i] = 0
                path.pop()
        backtracking(nums,used)
        return res

    def permuteUnique2(self, nums: [int]):
        res = []
        path = []
        used = [0] * len(nums)
        nums.sort()
        def backtracking(nums,used):
            if len(path) == len(nums):
                res.append(path[:])
                return
            for i in range(0, len(nums)):
                if i > 0 and nums[i] == nums[i-1] and used[i-1] == 0: # used[i-1]数层去重
                    continue
                if used[i] == 0: # 取过的信息不取
                    path.append(nums[i])
                    used[i] = 1
                    backtracking(nums,used)
                    path.pop()
                    used[i] = 0
        backtracking(nums,used)
        return res



if __name__ == '__main__':
    nums = [1, 1, 2]
    # nums.remove(nums)
    tmp = Solution()
    # res = tmp.permuteUnique(nums)
    res = tmp.permuteUnique2(nums)
    print(res)